package com.damin.liuxiaojing;

/**
 * @author ：cuiyuemin
 * @date ：Created in 2019-07-03 14:59
 */
public class HeapSort {
    public static void sort(int[] r) {
        int n = r.length;
        // 创建堆：对完全二叉树从下往上反复筛选的过程
        // n / 2 - 1为最后一个非叶子节点
        for (int i = n / 2 - 1; i >= 0; i--) {// 创建堆
            sift(r, i, n);
        }
        // 每趟将最小值交换到后面，再调整堆
        for (int i = n - 1; i > 0; i--) {
            int temp = r[0];
            r[0] = r[i];
            r[i] = temp;
            sift(r, 0, i);
        }
    }

    /**
     * 筛选法调整堆：调整前以low为根的子树的左子树和右子树都是大顶堆
     * 
     * @param r
     * @param low
     * @param high
     */
    public static void sift(int[] r, int low, int high) {
        // 变量初始化
        int rootIndex = low; // 子树的根
        int leftIndex = 2 * rootIndex + 1; // j为i结点的左孩子
        int rightIndex = leftIndex + 1;
        int temp = r[rootIndex];
        while (leftIndex < high) {
            int lesserIndex = leftIndex;
            if (rightIndex < high && r[leftIndex] > r[rightIndex]) {
                lesserIndex = rightIndex; // 数组元素比较,j为左右孩子的较小者
            }
            if (temp > r[lesserIndex]) { // 若父结点值较大
                r[rootIndex] = r[lesserIndex]; // 孩子结点中的较小值上移
                // 向下处理
                rootIndex = lesserIndex;
                leftIndex = 2 * rootIndex + 1;
                rightIndex = leftIndex + 1;
            } else {
                break;
            }
        }
        r[rootIndex] = temp; // 当前子树的原根值调整后的位置
    }

    public static void display(int[] r) {
        for (int item : r) {
            System.out.print(item + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] r = new int[] {3, 5, 5, 4, 120, 43, 1, 76, 78, 12, 346};
        HeapSort.sort(r);
        HeapSort.display(r);
    }
}
